package com.leetcode.optimize;

import org.testng.annotations.Test;

public class DistinctSubsequences {
	public int numDistinct(String S, String T) {
		int M = S.length();
		int N = T.length();
		char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		int[][] dp = new int[M+1][N+1];
		for (int i=0; i<=M; i++) dp[i][N] = 1;
		
		for (int i=N-1; i>=0; i--) {
			for (int j=M-1; j>=0; j--) {
				dp[j][i] = dp[j+1][i];
				if (s[j] == t[i]) {
					dp[j][i] += dp[j+1][i+1];
				}
			}
		}
		
        return dp[0][0];
    }
	
	@Test
	public void test1() {
		int n = new DistinctSubsequences().numDistinct("ccc", "c");
		System.out.println(n);
	}
}
